﻿#include<stdio.h>
#include<math.h>

#define N 4		//4*4的棋盘,4个皇后

int q[N + 1];	  //存储N皇后的列号

int check(int j) {
	int i;
	for (i = 1; i < j; i++) {		//检查第j个皇后的位置是否合法
		if (q[i] == q[j] || abs(i - j) == abs(q[i] - q[j])) {	 //判断是否在同一列和同一斜线上
			return 0;		//不合法
		}
	}

	return 1;	//合法
}	


void queen() {	//求解N皇后方案
	int i;
	for (i = 1; i <= N; i++) {	//每个皇后都还没上棋盘
		q[i] = 0;
	}

	int answer = 0;	//方案数

	int j = 1;	//正在摆放第j个皇后
	while (j >= 1) {
		q[j] = q[j] + 1;	//让第j个皇后向后一位摆放
		while (!check(j) && q[j] <= N) {		//判断第j个皇后的位置是否合法
			q[j] = q[j] + 1;	//不合法就往后一个位置摆放
		}

		if (q[j] <= N) {	//表示第j个皇后找到了一个合法摆放的位置
			if (j == N) {		//找到了N皇后的一组解
				answer = answer + 1;
				printf("方案%d:", answer);
				for (i = 1; i <= N; i++) {
					printf("%d", q[i]);
				}
				printf("\n");
			}
			else {	//继续摆放下一个皇后
				j = j + 1;
			}
		}
		else {	//表示第j个皇后找不到一个合法的摆放位置,回溯
			q[j] = 0;		//还原第j个皇后的位置
			j = j - 1;	//回溯
		}
	}
}
int main() {
	queen();
	return 0;
}